package com.ai.zuochengyun.phase01.class03;

/**
 * 单链表的爹题，这题能写会，链表就基本入门了
 */
public class Code11_FindFirstIntersectNode {

    public static Node getIntersectNode(Node head1, Node head2) {
        // 拿到两个链表的入环节点
        Node loop1 = getLoopNode(head1);
        Node loop2 = getLoopNode(head2);
        Node res = null;
        if (loop1 == null && loop2 == null) {
            res = noLoop(head1, head2);
        }
        if (loop1 != null && loop2 != null) {
            res = bothLoop(head1, head2, loop1, loop2);
        }
        return res;
    }

    /**
     * 获取链表是否有环
     * @param head
     * @return
     */
    public static Node getLoopNode(Node head) {
        // 形成环至少要三个节点
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }

        // 第一次两者相遇
        Node fast = head.next.next;
        Node slow = head.next;
        while (fast != slow) {
            // 快指针提前走到null，表示无环
            if (fast.next == null || fast.next.next == null) {
                break;
            }
            fast = fast.next.next;
            slow = slow.next;
        }

        // 相遇之后，调整快指针的步频，慢指针回到头节点，都改为走一步
        fast = fast.next;
        slow = slow.next;
        while (fast == slow) {
            if (fast == null || fast.next == null) {
                break;
            }
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     * 两个链表都没有环
     *
     * @param head1
     * @param head2
     * @return
     */
    public static Node noLoop(Node head1, Node head2) {
        if (head1 == null || head2 == null) {
            return null;
        }

        Node cur1 = head1;
        Node cur2 = head2;

        // 通过len来判断哪个链表更长
        // 如果len<0，说明head2所在的链表更长
        // 如果len=0，说明两个链表同等长
        // 如果len>0，说明head1所在的链表更长
        int len = 0;
        while (cur1.next != null) {
            len++;
            cur1 = cur1.next;
        }
        while (cur2.next != null) {
            len--;
            cur2 = cur2.next;
        }

        // 判断各自链表的最后一个节点，是否相同，如果不相同，则不相交
        if (cur1 != cur2) {
            return null;
        }

        // 如果两者不一样长，那么就让长链表现在两者长度差值的步数，然后让两个链表同时往下走
        len = Math.abs(len);
        // 谁长，谁就变成cur1；谁短，谁就变成head2
        cur1 = len < 0 ? head2 : head1;
        cur2 = cur1 == head1 ? head2 : head1;
        while (len != 0) {
            len--;
            cur1 = cur1 != null ? cur1.next : null;
        }

        // 从距离终点相同长度的位置出发，同时朝终点走，当两个节点的内存地址一样时，就表示两者相遇了
        while (cur1 != cur2) {
            cur1 = cur1 != null ? cur1.next : null;
            cur2 = cur2 != null ? cur2.next : null;
        }
        return cur1;
    }

    /**
     * 两个链表都有环
     *
     * @param loop1
     * @param loop2
     * @return
     */
    public static Node bothLoop(Node head1, Node head2, Node loop1, Node loop2) {
        Node cur1 = null, cur2 = null;

        // 这是第二种情况
        if (loop1 == loop2) {
            cur1 = head1;
            cur2 = head2;

            // 通过len来判断哪个链表更长
            // 如果len<0，说明head2所在的链表更长
            // 如果len=0，说明两个链表同等长
            // 如果len>0，说明head1所在的链表更长
            int len = 0;
            while (cur1 != loop1) {
                len++;
                cur1 = cur1.next;
            }
            while (cur2 != loop2) {
                len--;
                cur2 = cur2.next;
            }

            // 如果两者不一样长，那么就让长链表现在两者长度差值的步数，然后让两个链表同时往下走
            len = Math.abs(len);
            // 谁长，谁就变成cur1；谁短，谁就变成head2
            cur1 = len < 0 ? head2 : head1;
            cur2 = cur1 == head1 ? head2 : head1;
            while (len != 0) {
                len--;
                cur1 = cur1 != null ? cur1.next : null;
            }

            // 从距离终点相同长度的位置出发，同时朝终点走，当两个节点的内存地址一样时，就表示两者相遇了
            while (cur1 != cur2) {
                cur1 = cur1 != null ? cur1.next : null;
                cur2 = cur2 != null ? cur2.next : null;
            }
            return cur1;
        } else {
            // 第一种和第三种的情况
            cur1 = loop1.next;
            // 如果链表转了一圈，去和另一个loop2比对，遇上了，就返回；否则返回空
            while (cur1 != null) {
                if (cur1 == loop2) {
                    return cur1;
                }
                cur1 = cur1.next;
            }
            return cur1;
        }
    }

    private static class Node {
        int value;
        Node next;

        public Node(int value) {
            this.value = value;
        }

        public Node next(Node next) {
            this.next = next;
            return this;
        }
    }
}
